#include<iostream>
#include<fstream>
#include<time.h>
using namespace std;
clock_t start,stop;
double duration;

class MaxSS_1
{
	private :
	int Size, Times, A[];
	public :
	MaxSS_1(int N , int K)
	{
		Size = N;
		Times = K;
	}
	void SetA (int A[], int Size)
	{
		int i;
		ifstream inf("Data.txt");
		for (i = 0; i < Size; i++)
		{
			inf>>A[i];
		}
		inf.close();
	}
	int MaxSubsequenceSum(const int A[], int Size)
	{
		int ThisSum, MaxSum, i, j, k;
		MaxSum = 0;
		for (i = 0; i < Size; i++)
		{
			for (j = i; j < Size; j++)
			{
				ThisSum = 0;
				for (k = i; k <= j; k++)
					ThisSum = A[k] + ThisSum;
				if (ThisSum > MaxSum)
					MaxSum = ThisSum;
			}
		}
		return MaxSum;
	}
};

class MaxSS_4
{
	private :
	int Size, Times, A[];
	public :
	MaxSS_4(int N , int K)
	{
		Size = N;
		Times = K;
	}
	void SetA (int A[], int Size)
	{
		int i;
		ifstream inf("Data.txt");
		for (i = 0; i < Size; i++)
		{
			inf>>A[i];
		}
		inf.close();
	}
	int MaxSubsequenceSum(const int A[], int Size)
	{
		int ThisSum, MaxSum, i;
		ThisSum = MaxSum = 0;
		for (i = 0; i < Size; i++)
		{
			ThisSum += A[i];
			if (ThisSum > MaxSum)
				MaxSum = ThisSum;
			else if (ThisSum < 0)
				ThisSum = 0;
		}
		return MaxSum;
	}
};


main()
{
	int i, N, K, x;
	cout<<"Please input the number N:";
	cin>>N;
	cout<<endl;
	cout<<"How many times do you need?";
	cin>>K;
	
	cout<<"Please choose the algorithm you want:(1: Algorithm 1; 2: Algorithm 4)"<<endl;
	cin>>i;
	if (i == 1)
	{
		MaxSS_1 MSS1(N, K);
	
		int A[N];
		MSS1.SetA(A, N);
		x = 0;
		start = clock();
		for(int j = 0; j < K; j++)
			x = MSS1.MaxSubsequenceSum (A, N);
		stop = clock();
		duration = ((double)(stop-start))/CLK_TCK;
	}
	else if (i == 2)
	{
		MaxSS_4 MSS4(N, K);
	
		int A[N];
		MSS4.SetA(A, N);
		x = 0;
		start = clock();
		for(int j = 0; j < K; j++)
			x = MSS4.MaxSubsequenceSum (A, N);
		stop = clock();
		duration = ((double)(stop-start))/CLK_TCK;
	}
	else
	{
		cout<<"The number you choose is useless!"<<endl;
		return 0;
	}
	
	cout<<"The maxsum is "<<x<<endl;
	cout<<"The program runs "<<K<<" times."<<endl;
	cout<<"It takes "<<duration<<"s"<<endl;
	return 1;
}
